"""
请判断一个链表是否为回文链表。
输入: 1->2->2->1
输出: true

反转一个链表的同时记录元素，然后进行比较
"""


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        pre = None
        cur = head
        stack1 = []
        while cur:
            stack1.append(cur.val)
            temp = cur.next
            cur.next = pre
            pre = cur
            if not temp:break
            cur = temp
        while cur:
            if cur.val != stack1.pop(0):
                return False
            cur = cur.next
        return True

a1 = ListNode(1)
a2 = ListNode(1)
a3 = ListNode(2)
a4 = ListNode(1)
a3.next = a4
a2.next = a3
a1.next = a2

s = Solution()
print(s.isPalindrome(a1))